package leetCode;

import java.lang.reflect.Array;
import java.util.*;

/**
 * 136 只出现一次的数字
 * 数组/前后比对/运算
 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

 说明：

 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

 示例 1:
 输入: [2,2,1]
 输出: 1

 示例2:
 输入: [4,1,2,1,2]
 输出: 4
 */
public class SingleNumber {
    public static void main(String[] args) {
        System.out.println(singleNumberMe2(new int[]{2,2,1}));
    }

    //暴力，5/49，拉胯
    public static int singleNumberMe(int[] nums) {
        Map map = new HashMap();
        for (int i = 0;i < nums.length;i++) {
            if (!map.containsKey(nums[i])) {
                for (int j = i + 1;j< nums.length;j++) {
                    if (nums[i] == nums[j]) {
                        map.put(nums[i],"");
                        break;
                    }
                }
                if (!map.containsKey(nums[i])) {
                    return nums[i];
                }
            }
        }
        return 0;
    }

    //  set去重，15/51
    public static int singleNumberMe1(int[] nums) {
        HashSet<Integer> set = new HashSet();
        for (int i = 0;i< nums.length;i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        return set.iterator().next();
    }

    //  排序，26/55
    public static int singleNumberMe2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1;i<nums.length;i++){
            if (i == nums.length-1 && nums[i] != nums[i-1]) {
                return nums[i];
            }
            if (nums[i] != nums[i-1] && nums[i] != nums[i+1]) {
                return nums[i];
            }
        }
        return nums[0];
    }

    public static int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}
